//https://leetcode.cn/problems/arithmetic-slices-ii-subsequence/

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();

        unordered_map<long long, vector<int>> hash;

        vector<vector<int>> dp(n, vector<int>(n));

        for (int i = 0; i < n; i++) hash[nums[i]].push_back(i);
        int ret = 0;

        for (int i = 2; i < n; i++)
        {
            for (int j = i - 1; j >= 0; j--)
            {
                long long a = (long long)2 * nums[j] - nums[i];
                if (hash.count(a))
                {
                    for (auto k : hash[a])
                    {
                        if (k < j)
                            dp[i][j] += dp[j][k] + 1;
                    }
                }
                ret += dp[i][j];
            }
        }

        return ret;

    }
};